11590 - Prefix lookup/11590.3.cpp

   1 //WA!
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <sstream>
   7 #include <fstream>
   8 #include <cassert>
   9 #include <climits>
  10 #include <cstdlib>
  11 #include <cstring>
  12 #include <string>
  13 #include <cstdio>
  14 #include <vector>
  15 #include <cmath>
  16 #include <queue>
  17 #include <deque>
  18 #include <stack>
  19 #include <list>
  20 #include <map>
  21 #include <set>
  22
  23 #define D(x) cout << #x " = " << (x) << endl
  24
  25 typedef unsigned long long Int;
  26 const int BUFSIZE = 256;
  27 char buf[BUFSIZE];
  28
  29 int M;
  30 map<string, Int> ans;
  31
  32 struct node{
  33   node * left, * right;
  34   bool end; //is this node a complete prefix?
  35   node(bool e) : end(e) {
  36     left = right = NULL;
  37   }
  38 };
  39
  40 //not used, because I love to waste memory (makes me feel sexy)
  41 void clean(node * n){
  42   if (n == NULL) return;
  43   clean(n->left); clean(n->right);
  44   delete n;
  45 }
  46
  47 Int f(string s, node * n){ //s = string built so far, n = the node we are standing at
  48   Int left = 0, right = 0, ret = 0;
  49   if (n->left != NULL){
  50     left = f(s + "0", n->left);
  51   }
  52   if (n->right != NULL){
  53     right = f(s + "1", n->right);
  54   }
  55   ret += left + right;
  56
  57   if (n->end){
  58     Int howmany;
  59     if (M - s.size() < 64){ //we are safe from overflow
  60       Int x = ((1ULL) << (M - s.size())); //2^(m - |s|)
  61       howmany = x - left - right;
  62     }else{ //2^64 overflows!
  63       Int x = 0;
  64       x = ~x; // (x = ~0ULL) <-> (x = 2^64 - 1)
  65       howmany = x - left - right + 1;
  66     }
  67     ret += howmany;
  68     ans[s] = howmany;
  69   }
  70   return ret;
  71 }
  72
  73 int main(){
  74   int n;
  75   while (scanf("%d %d", &n, &M)==2 && !(n == 0 && M == 0)){
  76     assert(getchar() == '\n');
  77     assert(n > 0);
  78     assert(M > 0);
  79     //D(n); D(M);
  80     ans.clear();
  81     node * root = new node(true);
  82     while (n--){
  83       fgets(buf, BUFSIZE, stdin);
  84       assert(buf[0] != '*');
  85       node * cur = root;
  86       for (int i=0; ; ++i){
  87         if (buf[i] == '*'){
  88           cur->end = true;
  89           break;
  90         }
  91         if (buf[i] == '0'){
  92           if (cur->left == NULL) cur->left = new node(false);
  93           cur = cur->left;
  94         }else if (buf[i] == '1'){
  95           if (cur->right == NULL) cur->right = new node(false);
  96           cur = cur->right;
  97         }
  98       }
  99     }
 100
 101     f("", root);
 102
 103     int K;
 104     scanf("%d", &K);
 105     assert(getchar() == '\n');
 106     while (K--){
 107       fgets(buf, BUFSIZE, stdin);
 108       buf[strlen(buf)-2] = '\0'; //delete *\n
 109       Int t = ans[string(buf)];
 110       assert(t >= 0);
 111       printf("%llu\n", t);
 112     }
 113
 114     assert(getchar() == '\n'); //empty line
 115     puts("");
 116   }
 117   return 0;
 118 }